/**
 * @file perform.cpp
 * @author Xin Yuan
 *
 * Modified by Alejandro Cabrera:
 *  - Removed all magic numbers and replaced them with global, clear constants
 *  - Added some comments
 *  - main() meets C standard
 *
 * This program is developed for cop4610 project no. 4
 * It will be used to test the efficiency (and correctness) 
 * of your memory management library.
 * To run with system built-in memory management:
 * 
 * > g++ heapsort.cpp
 * > a.out > sys.out
 * 
 * To run with your own memory managment library:
 * 
 * > g++ -DMYMEM heapsort.cpp mm1.o
 * > a.out > my.out
 *
 * use 'diff my.out sys.out' to check if your library is correct.
 */

#include <cmath>
#include <cstdint>
#include <cstdio>

#ifndef MYMEM
#include <cstdlib>
#define MyMemAlloc(x) malloc((x))
#define MyMemFree(x) free((x))
#endif

#ifdef MYMEM
#define MyMemAlloc(x) m.mymalloc((x))
#define MyMemFree(x) m.myfree((x))
#include "../include/mm.h"
static const uint32_t MEMORY_SIZE = 50500000;
static const uint32_t LIST_SIZE = 2000000;
MemoryManager m(MEMORY_SIZE, LIST_SIZE);
#endif

using namespace std;

struct node {
  int val;
  struct node *left;
  struct node *right;
};

struct node *tree;

static const uint32_t NUM_INITIAL_NODES = 10000;
static const uint32_t MAX_NODE_VAL = 10000000;
static const uint32_t ITERATIONS = 3000000;

void insert_node(int x)
{
  struct node *t, *t1, *t2;
  int *tmp;

  tmp = (int *) MyMemAlloc(sizeof(int));
  *tmp = x;
  
  // if no elements have been inserted yet, insert this element
  // and return
  if (tree == NULL) { 
    tree = (struct node *) MyMemAlloc(sizeof(struct node));
    tree->left = NULL;
    tree->right = NULL;
    tree->val = *tmp;
    MyMemFree(tmp);
    return;
  } 

  // navigate through the tree, looking for place to insert value
  // if the value is found, return.
  t = tree;
  while (t != NULL) {
    if (*tmp > t->val) {
      t1 = t;
      t = t->right;
    } 
    else if (*tmp < t->val) {
      t1 = t;
      t = t->left;
    } 
    else {
      MyMemFree(tmp);
      return; 
    }
  }

  // allocate a new node to store the value
  t2 = (struct node *) MyMemAlloc(sizeof(node));
  t2->val = *tmp;
  t2->left = NULL;
  t2->right = NULL;

  // insert the value at the right location
  if (t1->val > *tmp) 
    t1->left = t2;
  else 
    t1->right = t2;

  MyMemFree(tmp);
}

// here we only delete the header node
void delete_node() 
{  
  static int pos = 0;
  struct node *t, *t1, *t2;

  // if there is no node to delete, return
  if (tree == NULL) 
    return;

  // If the left sub tree does not exist, delete the root
  // node and set the root of the tree to be the right sub tree
  if (tree->left == NULL) {
    t = tree;
    tree = tree->right;
    MyMemFree(t);
    return;
  }

  // vice-versa to above
  if (tree->right == NULL) {
    t = tree;
    tree = tree->left;
    MyMemFree(t);
    return;
  }

  if (pos == 0) {
    pos = 1;
    t = tree->left;
    t1 = 0;

    while (t->right != 0) {
      t1 = t;
      t = t->right;
    }

    if (t1 == 0) {
      t1 = tree;
      t->right = tree->right;
      MyMemFree(t1);
      tree = t;
      return;
    } 
    else {
      t1->right = t->left;
      t2 = tree;
      t->left = tree->left;
      t->right = tree->right;
      MyMemFree(t2);
      tree = t;
      return;
    }
  } 
  else if (pos != 0) {
    pos = 0;
    t = tree->right;
    t1 = NULL;

    while (t->left != 0) {
      t1 = t;
      t = t->left;
    }
    
    if (t1 == 0) {
      t1 = tree;
      t->left = tree->left;
      MyMemFree(t1);
      tree = t;
      return;
    } 
    else {
      t1->left = t->right;
      t2 = tree;
      t->left = tree->left;
      t->right = tree->right;
      MyMemFree(t2);
      tree = t;
      return;
    }
  }
}

void inorder(struct node *t)
{
  if (t == NULL) 
    return;
  inorder(t->left);
  //  printf("%d\n", t->val);
  inorder(t->right);
}

int main() 
{
  tree = NULL;

  for (size_t i = 0; i < NUM_INITIAL_NODES; ++i) 
    insert_node((int)random() % MAX_NODE_VAL);

  for (size_t i = 0; i < ITERATIONS; ++i) {
    if (random() % 2 == 0) 
      delete_node();
    else 
      insert_node(random() % MAX_NODE_VAL);
  }
  inorder(tree);

  return 0;
}
